package acwing.单调队列;

import java.io.*;

/**
 * @description:
 * @author: qian
 * @createDate: 2021/11/15
 */
public class 滑动窗口 {

    private static int N = 1000010;
    private static int[] a = new int [N];
    private static int[] q = new int [N];// 存下标

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] s = br.readLine().split(" ");
        int n = Integer.parseInt(s[0]); // 数组长度
        int k = Integer.parseInt(s[1]); // 窗口长度
        String[] s1 = br.readLine().split(" ");
        for(int i = 0;i<n;i++) {
            a[i] = Integer.parseInt(s1[i]);
        }

        int hh = 0; // 头
        int tt = -1; // 尾
        for (int i = 0; i < n; i++) {
            if (hh <= tt && i - k + 1 > q[hh]) hh++;
            while (hh <= tt && a[q[tt]] >= a[i]) tt--;
            q[++ tt] = i;
            if (i >= k - 1) {
                bw.write(a[q[hh]]+" ");
            }
        }
        bw.write("\n");
        hh = 0;
        tt = -1;
        for (int i = 0; i < n; i++) {
            if (hh <= tt && i - k + 1 > q[hh]) hh++;
            while (hh <= tt && a[q[tt]] <= a[i]) tt--;
            q[++ tt] = i;
            if (i >= k - 1) {
                bw.write(a[q[hh]]+" ");
            }
        }
        bw.flush();
        bw.close();
        br.close();

    }
}
